import copy


class Solution:
    def maxTrailingZeros(self, grid):
        def cal(value):
            count_5 = 0
            count_2 = 0
            while value % 10 == 0:
                value = value // 10
                count_5 += 1
                count_2 += 1
            while value % 5 == 0:
                value = value // 5
                count_5 += 1
            while value % 2 == 0:
                value = value // 2
                count_2 += 1
            return count_5, count_2

        m = len(grid)
        n = len(grid[0])
        for i in range(m):
            for j in range(n):
                grid[i][j] = list(cal((grid[i][j])))
        DP1 = copy.deepcopy(grid)
        DP3 = copy.deepcopy(grid)
        for i in range(m):
            for j in range(n):
                if j == 0:
                    DP1[i][j][0] = grid[i][j][0]
                    DP1[i][j][1] = grid[i][j][1]
                else:
                    DP1[i][j][0] = grid[i][j][0] + DP1[i][j - 1][0]
                    DP1[i][j][1] = grid[i][j][1] + DP1[i][j - 1][1]
        for j in range(n):
            for i in range(m):
                if i == 0:
                    DP3[i][j][0] = grid[i][j][0]
                    DP3[i][j][1] = grid[i][j][1]
                else:
                    DP3[i][j][0] = grid[i][j][0] + DP3[i - 1][j][0]
                    DP3[i][j][1] = grid[i][j][1] + DP3[i - 1][j][1]
        max_value = -1

        def judge_zero(count_5, count_2):
            return min(count_5, count_2)

        for i in range(m):
            for j in range(n):
                road_1 = [DP1[i][j][0] + DP3[i][j][0] - grid[i][j][0], DP1[i][j][1] + DP3[i][j][1] - grid[i][j][1]]
                zero_1 = judge_zero(road_1[0], road_1[1])
                road_2 = [DP1[i][-1][0] - DP1[i][j][0] + DP3[i][j][0],
                          DP1[i][-1][1] - DP1[i][j][1] + DP3[i][j][1]]
                zero_2 = judge_zero(road_2[0], road_2[1])
                road_3 = [DP1[i][j][0] + DP3[-1][j][0] - DP3[i][j][0],
                          DP1[i][j][1] + DP3[-1][j][1] - DP3[i][j][1]]
                zero_3 = judge_zero(road_3[0], road_3[1])
                road_4 = [DP1[i][-1][0] - DP1[i][j][0] + DP3[-1][j][0] - DP3[i][j][0] + grid[i][j][0],
                          DP1[i][-1][1] - DP1[i][j][1] + DP3[-1][j][1] - DP3[i][j][1] + grid[i][j][1]]
                zero_4 = judge_zero(road_4[0], road_4[1])
                max_value = max(max_value, zero_1, zero_2, zero_3, zero_4)
        return max_value


data = Solution()
# grid = [[23, 17, 15, 3, 20], [8, 1, 20, 27, 11], [9, 4, 6, 2, 21], [40, 9, 1, 10, 6], [22, 7, 4, 5, 3]]
# print(data.maxTrailingZeros(grid))
grid = [[899, 727, 165, 249, 531, 300, 542, 890], [981, 587, 565, 943, 875, 498, 582, 672],
        [106, 902, 524, 725, 699, 778, 365, 220]]
print(data.maxTrailingZeros(grid))
